package com.xjl.sort;

import com.xjl.utils.SortUtil;

/**
 * @描述：
 * @作者： 许JIAN林
 */
public class QuickSort {

    public static void quicksort(int[] arr, int L, int R) {
        if (L < R) {
            int[] p = partition(arr, L, R);
            quicksort(arr, L,p[0] -1);
            quicksort(arr,p[1] +1, R);
        }
    }


    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R ;
        int flag = arr[R];

        while(L < more ){
            if (arr[L] < flag){
                SortUtil.swap(arr, ++less, L++);
            }else if (arr[L] > flag){
                SortUtil.swap(arr, --more, L);
            }else{
                L++;
            }
        }
        SortUtil.swap(arr, R, more);
        return new int[] {less + 1, more};

    }

    public static void main(String[] args) {
        int[] arr = new int[] {6,3,7,4,5};
        quicksort(arr, 0, arr.length - 1);
        SortUtil.display(arr);
    }
}
